package codetop.microsoft.T124;

import util.TreeNode;

/**
 * @Author: 18362
 * @Create: 2022-08-12 22:14:37 星期五
 */

class Solution {
    private int maxPath = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int max = getPath(root);
        return Math.max(max, maxPath);
    }
    private int getPath(TreeNode root) {
        if (root == null)
            return 0;
        int left = getPath(root.left), right = getPath(root.right);
        if (root.left == null && root.right == null) {
            maxPath = Math.max(maxPath, root.val);
        } else if (root.left == null || root.right == null) {
            maxPath = Math.max(maxPath, root.left == null ? right : left);
        } else {
            maxPath = Math.max(maxPath, Math.max(left + right + root.val, Math.max(left, right)));
        }
        return Math.max(root.val, root.val + Math.max(left, right));
    }
}
